package string

// 1392. 最长快乐前缀
// https://leetcode-cn.com/problems/longest-happy-prefix/
func GetlongestPrefix(s string) string {
	next := GetNext(s)
	n := next[len(s)]
	return s[0:n]
}

//获得Next数组
func GetNext(s string) []int {
	sLen := len(s)
	next := make([]int, sLen+1)
	next[0] = -1
	i, j := 0, -1
	for i < sLen {
		if j == -1 || s[i] == s[j] {
			i++
			j++
			next[i] = j
		} else {
			j = next[j]
		}
	}

	return next
}
